package com.leetcode.code;

import com.leetcode.base.ListNode;

/**
 * 已发
 */
public class LeetCode0142Java {
    public static void main(String[] args) {
        Solution solution = new Solution();
    }

    static class Solution {
        public ListNode detectCycle(ListNode head) {
            if (head == null || head.next == null || head.next.next == null) {
                return null;
            }

            ListNode fast = head.next.next;
            ListNode slow = head.next;

            //        while (true) {
            //            if (fast == null || fast.next == null)
            //                return null; // 说明没有环
            //            else if (fast == slow || fast.next == slow) {
            //                // 说明有环
            //                return slow;
            //            } else {
            //                fast = fast.next.next;
            //                slow = slow.next;
            //            }
            //        }

            while (fast != slow) {
                if (fast.next == null || fast.next.next == null) {
                    return null;
                } else {
                    fast = fast.next.next;
                    slow = slow.next;
                }
            }
            //说明有环
            fast = head;
            //变成一次走一步，快慢指针再次相遇的时候肯定在入环节点上,可用数学归纳法证明
            //https://blog.csdn.net/jhlovetll/article/details/85255708
            while (fast != slow) {
                fast = fast.next;
                slow = slow.next;
            }

            return slow;
        }
    }
}
